#include <graph.h>
Public Types | |
typedef int | node_id |
terminals | |
typedef arc * | arc_id |
SOURCE = 0 | |
SINK = 1 | |
enum | termtype { SOURCE = 0, SINK = 1 } |
Public Member Functions | |
Graph (int node_num_max, int edge_num_max, void(*err_function)(char *)=NULL) | |
(should be enough for most applications) | |
~Graph () | |
Destructor. | |
node_id | add_node (int num=1) |
void | add_edge (node_id i, node_id j, captype cap, captype rev_cap) |
void | add_tweights (node_id i, tcaptype cap_source, tcaptype cap_sink) |
flowtype | maxflow (bool reuse_trees=false, Block< node_id > *changed_list=NULL) |
termtype | what_segment (node_id i, termtype default_segm=SOURCE) |
void | reset () |
arc_id | get_first_arc () |
arc_id | get_next_arc (arc_id a) |
int | get_node_num () |
other functions for reading graph structure | |
int | get_arc_num () |
void | get_arc_ends (arc_id a, node_id &i, node_id &j) |
tcaptype | get_trcap (node_id i) |
returns residual capacity of SOURCE->i minus residual capacity of i->SINK | |
captype | get_rcap (arc *a) |
returns residual capacity of arc a | |
void | set_trcap (node_id i, tcaptype trcap) |
void | set_rcap (arc *a, captype rcap) |
void | mark_node (node_id i) |
void | remove_from_changed_list (node_id i) |
void | start_save () |
void | stop_save () |
void | restore_arc (arc *dest, const arc &s) |
void | restore_node (node *dest, const node &s) |
void | restore_saved () |
void | save_node (node *x) |
void | save_arc (arc *x) |
void | save (node *x) |
void | save (node &x) |
void | save (arc *x) |
void | save (arc &x) |
Public Attributes | |
graph_save | save |
Private Member Functions | |
void | reallocate_nodes (int num) |
monotonically increasing global counter | |
void | reallocate_arcs () |
num is the number of new nodes | |
void | set_active (node *i) |
functions for processing active list | |
node * | next_active () |
void | set_orphan_front (node *i) |
functions for processing orphans list | |
void | set_orphan_rear (node *i) |
add to the beginning of the list | |
void | add_to_changed_list (node *i) |
add to the end of the list | |
void | maxflow_init () |
void | maxflow_reuse_trees_init () |
called if reuse_trees == false | |
void | augment (arc *middle_arc) |
called if reuse_trees == true | |
void | process_source_orphan (node *i) |
void | process_sink_orphan (node *i) |
void | test_consistency (node *current_node=NULL) |
Private Attributes | |
node * | nodes |
node * | node_last |
node * | node_max |
node_last = nodes+node_num, node_max = nodes+node_num_max; | |
arc * | arcs |
arc * | arc_last |
arc * | arc_max |
arc_last = arcs+2*edge_num, arc_max = arcs+2*edge_num_max; | |
int | node_num |
DBlock< nodeptr > * | nodeptr_block |
void(* | error_function )(char *) |
flowtype | flow |
int | maxflow_iteration |
reusing trees & list of changed pixels | |
Block< node_id > * | changed_list |
counter | |
node * | queue_first [2] |
node * | queue_last [2] |
nodeptr * | orphan_first |
list of active nodes | |
nodeptr * | orphan_last |
int | TIME |
list of pointers to orphans | |
Static Private Attributes | |
static const int | NODEPTR_BLOCK_SIZE = 128 |
Classes | |
struct | arc |
class | graph_save |
debug function More... | |
struct | node |
internal variables and functions More... | |
struct | nodeptr |
captype: type of edge capacities (excluding t-links) tcaptype: type of t-links (edges between nodes and terminals) flowtype: type of total flow
Definition at line 57 of file graph.h.
typedef arc* Graph< captype, tcaptype, flowtype >::arc_id |
The following two functions return arcs in the same order that they were added to the graph. NOTE: for each call add_edge(i,j,cap,cap_rev) the first arc returned will be i->j, and the second j->i. If there are no more arcs, then the function can still be called, but the returned arc_id is undetermined.
enum Graph::termtype |
Graph< captype, tcaptype, flowtype >::Graph | ( | int | node_num_max, | |
int | edge_num_max, | |||
void(*)(char *) | err_function = NULL | |||
) |
(should be enough for most applications)
Constructor. The first argument gives an estimate of the maximum number of nodes that can be added to the graph, and the second argument is an estimate of the maximum number of edges. The last (optional) argument is the pointer to the function which will be called if an error occurs; an error message is passed to this function. If this argument is omitted, exit(1) will be called.
IMPORTANT: It is possible to add more nodes to the graph than node_num_max (and node_num_max can be zero). However, if the count is exceeded, then the internal memory is reallocated (increased by 50%) which is expensive. Also, temporarily the amount of allocated memory would be more than twice than needed. Similarly for edges. If you wish to avoid this overhead, you can download version 2.2, where nodes and edges are stored in blocks.
Definition at line 12 of file graph.cpp.
00013 : node_num(0), 00014 nodeptr_block(NULL), 00015 error_function(err_function) 00016 { 00017 if (node_num_max < 16) node_num_max = 16; 00018 if (edge_num_max < 16) edge_num_max = 16; 00019 00020 nodes = (node*) malloc(node_num_max*sizeof(node)); 00021 arcs = (arc*) malloc(2*edge_num_max*sizeof(arc)); 00022 if (!nodes || !arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); } 00023 00024 node_last = nodes; 00025 node_max = nodes + node_num_max; 00026 arc_last = arcs; 00027 arc_max = arcs + 2*edge_num_max; 00028 00029 maxflow_iteration = 0; 00030 flow = 0; 00031 }
Graph< captype, tcaptype, flowtype >::~Graph | ( | ) |
Destructor.
Definition at line 34 of file graph.cpp.
00035 { 00036 if (nodeptr_block) 00037 { 00038 delete nodeptr_block; 00039 nodeptr_block = NULL; 00040 } 00041 free(nodes); 00042 free(arcs); 00043 }
void Graph< captype, tcaptype, flowtype >::add_edge | ( | node_id | i, | |
node_id | j, | |||
captype | cap, | |||
captype | rev_cap | |||
) | [inline] |
Adds a bidirectional edge between 'i' and 'j' with the weights 'cap' and 'rev_cap'. IMPORTANT: see note about the constructor
Definition at line 517 of file graph.h.
00518 { 00519 assert(_i >= 0 && _i < node_num); 00520 assert(_j >= 0 && _j < node_num); 00521 assert(_i != _j); 00522 assert(cap >= 0); 00523 assert(rev_cap >= 0); 00524 00525 if (arc_last == arc_max) reallocate_arcs(); 00526 00527 arc *a = arc_last ++; 00528 arc *a_rev = arc_last ++; 00529 00530 node* i = nodes + _i; 00531 node* j = nodes + _j; 00532 00533 a -> sister = a_rev; 00534 a_rev -> sister = a; 00535 a -> next = i -> first; 00536 i -> first = a; 00537 a_rev -> next = j -> first; 00538 j -> first = a_rev; 00539 a -> head = j; 00540 a_rev -> head = i; 00541 a -> r_cap = cap; 00542 a_rev -> r_cap = rev_cap; 00543 }
Graph< captype, tcaptype, flowtype >::node_id Graph< captype, tcaptype, flowtype >::add_node | ( | int | num = 1 |
) | [inline] |
Adds node(s) to the graph. By default, one node is added (num=1); then first call returns 0, second call returns 1, and so on. If num>1, then several nodes are added, and node_id of the first one is returned. IMPORTANT: see note about the constructor
Definition at line 476 of file graph.h.
00477 { 00478 assert(num > 0); 00479 00480 if (node_last + num > node_max) reallocate_nodes(num); 00481 00482 if (num == 1) 00483 { 00484 node_last -> first = NULL; 00485 node_last -> tr_cap = 0; 00486 node_last -> is_marked = 0; 00487 node_last -> is_in_changed_list = 0; 00488 00489 node_last ++; 00490 return node_num++; 00491 } 00492 else 00493 { 00494 memset(node_last, 0, num*sizeof(node)); 00495 00496 node_id i = node_num; 00497 node_num += num; 00498 node_last += num; 00499 return i; 00500 } 00501 }
void Graph< captype, tcaptype, flowtype >::add_to_changed_list | ( | node * | i | ) | [inline, private] |
add to the end of the list
Definition at line 107 of file maxflow.cpp.
00108 { 00109 if (changed_list && !i->is_in_changed_list) 00110 { 00111 node_id* ptr = changed_list->New(); 00112 *ptr = (node_id)(i - nodes); 00113 i->is_in_changed_list = true; 00114 } 00115 }
void Graph< captype, tcaptype, flowtype >::add_tweights | ( | node_id | i, | |
tcaptype | cap_source, | |||
tcaptype | cap_sink | |||
) | [inline] |
Adds new edges 'SOURCE->i' and 'i->SINK' with corresponding weights. Can be called multiple times for each node. Weights can be negative. NOTE: the number of such edges is not counted in edge_num_max. No internal memory is allocated by this call.
Definition at line 504 of file graph.h.
00505 { 00506 assert(i >= 0 && i < node_num); 00507 00508 tcaptype delta = nodes[i].tr_cap; 00509 if (delta > 0) cap_source += delta; 00510 else cap_sink -= delta; 00511 flow += (cap_source < cap_sink) ? cap_source : cap_sink; 00512 save(nodes[i]); 00513 nodes[i].tr_cap = cap_source - cap_sink; 00514 }
void Graph< captype, tcaptype, flowtype >::augment | ( | arc * | middle_arc | ) | [private] |
called if reuse_trees == true
Definition at line 245 of file maxflow.cpp.
00246 { 00247 node *i; 00248 arc *a; 00249 tcaptype bottleneck; 00250 00251 00252 /* 1. Finding bottleneck capacity */ 00253 /* 1a - the source tree */ 00254 bottleneck = middle_arc -> r_cap; 00255 for (i=middle_arc->sister->head; ; i=a->head) 00256 { 00257 a = i -> parent; 00258 if (a == TERMINAL) break; 00259 if (bottleneck > a->sister->r_cap) bottleneck = a -> sister -> r_cap; 00260 } 00261 if (bottleneck > i->tr_cap) bottleneck = i -> tr_cap; 00262 /* 1b - the sink tree */ 00263 for (i=middle_arc->head; ; i=a->head) 00264 { 00265 a = i -> parent; 00266 if (a == TERMINAL) break; 00267 if (bottleneck > a->r_cap) bottleneck = a -> r_cap; 00268 } 00269 if (bottleneck > - i->tr_cap) bottleneck = - i -> tr_cap; 00270 00271 00272 /* 2. Augmenting */ 00273 /* 2a - the source tree */ 00274 save(middle_arc -> sister); 00275 middle_arc -> sister -> r_cap += bottleneck; 00276 save(middle_arc); 00277 middle_arc -> r_cap -= bottleneck; 00278 for (i=middle_arc->sister->head; ; i=a->head) 00279 { 00280 a = i -> parent; 00281 if (a == TERMINAL) break; 00282 save(a); 00283 a -> r_cap += bottleneck; 00284 save(a -> sister); 00285 a -> sister -> r_cap -= bottleneck; 00286 if (!a->sister->r_cap) 00287 { 00288 set_orphan_front(i); // add i to the beginning of the adoption list 00289 } 00290 } 00291 save(i); 00292 i -> tr_cap -= bottleneck; 00293 if (!i->tr_cap) 00294 { 00295 set_orphan_front(i); // add i to the beginning of the adoption list 00296 } 00297 /* 2b - the sink tree */ 00298 for (i=middle_arc->head; ; i=a->head) 00299 { 00300 a = i -> parent; 00301 if (a == TERMINAL) break; 00302 save(a->sister); 00303 a -> sister -> r_cap += bottleneck; 00304 save(a); 00305 a -> r_cap -= bottleneck; 00306 if (!a->r_cap) 00307 { 00308 set_orphan_front(i); // add i to the beginning of the adoption list 00309 } 00310 } 00311 save(i); 00312 i -> tr_cap += bottleneck; 00313 if (!i->tr_cap) 00314 { 00315 set_orphan_front(i); // add i to the beginning of the adoption list 00316 } 00317 00318 flow += bottleneck; 00319 }
void Graph< captype, tcaptype, flowtype >::get_arc_ends | ( | arc_id | a, | |
node_id & | i, | |||
node_id & | j | |||
) |
int Graph< captype, tcaptype, flowtype >::get_arc_num | ( | ) | [inline] |
arc_id Graph< captype, tcaptype, flowtype >::get_next_arc | ( | arc_id | a | ) |
int Graph< captype, tcaptype, flowtype >::get_node_num | ( | ) | [inline] |
void Graph< captype, tcaptype, flowtype >::mark_node | ( | node_id | i | ) | [inline] |
If flag reuse_trees is true while calling maxflow(), then search trees are reused from previous maxflow computation. In this case before calling maxflow() the user must specify which parts of the graph have changed by calling mark_node(): add_tweights(i),set_trcap(i) => call mark_node(i) add_edge(i,j),set_rcap(a) => call mark_node(i); mark_node(j)
This option makes sense only if a small part of the graph is changed. The initialization procedure goes only through marked nodes then.
mark_node(i) can either be called before or after graph modification. Can be called more than once per node, but calls after the first one do not have any effect.
NOTE:
Definition at line 609 of file graph.h.
00610 { 00611 node* i = nodes + _i; 00612 if (!i->next) 00613 { 00614 /* it's not in the list yet */ 00615 if (queue_last[1]) queue_last[1] -> next = i; 00616 else queue_first[1] = i; 00617 queue_last[1] = i; 00618 i -> next = i; 00619 } 00620 i->is_marked = 1; 00621 }
flowtype Graph< captype, tcaptype, flowtype >::maxflow | ( | bool | reuse_trees = false , |
|
Block< node_id > * | changed_list = NULL | |||
) |
Computes the maxflow. Can be called several times. FOR DESCRIPTION OF reuse_trees, SEE mark_node(). FOR DESCRIPTION OF changed_list, SEE remove_from_changed_list().
Definition at line 480 of file maxflow.cpp.
00481 { 00482 node *i, *j, *current_node = NULL; 00483 arc *a; 00484 nodeptr *np, *np_next; 00485 00486 if (!nodeptr_block) 00487 { 00488 nodeptr_block = new DBlock<nodeptr>(NODEPTR_BLOCK_SIZE, error_function); 00489 } 00490 00491 changed_list = _changed_list; 00492 if (maxflow_iteration == 0 && reuse_trees) { if (error_function) (*error_function)("reuse_trees cannot be used in the first call to maxflow()!"); exit(1); } 00493 if (changed_list && !reuse_trees) { if (error_function) (*error_function)("changed_list cannot be used without reuse_trees!"); exit(1); } 00494 00495 if (reuse_trees) maxflow_reuse_trees_init(); 00496 else maxflow_init(); 00497 00498 // main loop 00499 while ( 1 ) 00500 { 00501 // test_consistency(current_node); 00502 00503 if ((i=current_node)) 00504 { 00505 i -> next = NULL; /* remove active flag */ 00506 if (!i->parent) i = NULL; 00507 } 00508 if (!i) 00509 { 00510 if (!(i = next_active())) break; 00511 } 00512 00513 /* growth */ 00514 if (!i->is_sink) 00515 { 00516 /* grow source tree */ 00517 for (a=i->first; a; a=a->next) 00518 if (a->r_cap) 00519 { 00520 j = a -> head; 00521 if (!j->parent) 00522 { 00523 j -> is_sink = 0; 00524 j -> parent = a -> sister; 00525 j -> TS = i -> TS; 00526 j -> DIST = i -> DIST + 1; 00527 set_active(j); 00528 add_to_changed_list(j); 00529 } 00530 else if (j->is_sink) break; 00531 else if (j->TS <= i->TS && 00532 j->DIST > i->DIST) 00533 { 00534 /* heuristic - trying to make the distance from j to the source shorter */ 00535 j -> parent = a -> sister; 00536 j -> TS = i -> TS; 00537 j -> DIST = i -> DIST + 1; 00538 } 00539 } 00540 } 00541 else 00542 { 00543 /* grow sink tree */ 00544 for (a=i->first; a; a=a->next) 00545 if (a->sister->r_cap) 00546 { 00547 j = a -> head; 00548 if (!j->parent) 00549 { 00550 j -> is_sink = 1; 00551 j -> parent = a -> sister; 00552 j -> TS = i -> TS; 00553 j -> DIST = i -> DIST + 1; 00554 set_active(j); 00555 add_to_changed_list(j); 00556 } 00557 else if (!j->is_sink) { a = a -> sister; break; } 00558 else if (j->TS <= i->TS && 00559 j->DIST > i->DIST) 00560 { 00561 /* heuristic - trying to make the distance from j to the sink shorter */ 00562 j -> parent = a -> sister; 00563 j -> TS = i -> TS; 00564 j -> DIST = i -> DIST + 1; 00565 } 00566 } 00567 } 00568 00569 TIME ++; 00570 00571 if (a) 00572 { 00573 i -> next = i; /* set active flag */ 00574 current_node = i; 00575 00576 /* augmentation */ 00577 augment(a); 00578 /* augmentation end */ 00579 00580 /* adoption */ 00581 while ((np=orphan_first)) 00582 { 00583 np_next = np -> next; 00584 np -> next = NULL; 00585 00586 while ((np=orphan_first)) 00587 { 00588 orphan_first = np -> next; 00589 i = np -> ptr; 00590 nodeptr_block -> Delete(np); 00591 if (!orphan_first) orphan_last = NULL; 00592 if (i->is_sink) process_sink_orphan(i); 00593 else process_source_orphan(i); 00594 } 00595 00596 orphan_first = np_next; 00597 } 00598 /* adoption end */ 00599 } 00600 else current_node = NULL; 00601 } 00602 // test_consistency(); 00603 00604 if (!reuse_trees || (maxflow_iteration % 64) == 0) 00605 { 00606 delete nodeptr_block; 00607 nodeptr_block = NULL; 00608 } 00609 00610 maxflow_iteration ++; 00611 return flow; 00612 }
void Graph< captype, tcaptype, flowtype >::maxflow_init | ( | ) | [private] |
Definition at line 120 of file maxflow.cpp.
00121 { 00122 node *i; 00123 00124 queue_first[0] = queue_last[0] = NULL; 00125 queue_first[1] = queue_last[1] = NULL; 00126 orphan_first = NULL; 00127 00128 TIME = 0; 00129 00130 for (i=nodes; i<node_last; i++) 00131 { 00132 i -> next = NULL; 00133 i -> is_marked = 0; 00134 i -> is_in_changed_list = 0; 00135 i -> TS = TIME; 00136 if (i->tr_cap > 0) 00137 { 00138 /* i is connected to the source */ 00139 i -> is_sink = 0; 00140 i -> parent = TERMINAL; 00141 set_active(i); 00142 i -> DIST = 1; 00143 } 00144 else if (i->tr_cap < 0) 00145 { 00146 /* i is connected to the sink */ 00147 i -> is_sink = 1; 00148 i -> parent = TERMINAL; 00149 set_active(i); 00150 i -> DIST = 1; 00151 } 00152 else 00153 { 00154 i -> parent = NULL; 00155 } 00156 } 00157 }
void Graph< captype, tcaptype, flowtype >::maxflow_reuse_trees_init | ( | ) | [private] |
called if reuse_trees == false
Definition at line 160 of file maxflow.cpp.
00161 { 00162 node* i; 00163 node* j; 00164 node* queue = queue_first[1]; 00165 arc* a; 00166 nodeptr* np; 00167 00168 queue_first[0] = queue_last[0] = NULL; 00169 queue_first[1] = queue_last[1] = NULL; 00170 orphan_first = orphan_last = NULL; 00171 00172 TIME ++; 00173 00174 while ((i=queue)) 00175 { 00176 queue = i->next; 00177 if (queue == i) queue = NULL; 00178 i->next = NULL; 00179 i->is_marked = 0; 00180 set_active(i); 00181 00182 if (i->tr_cap == 0) 00183 { 00184 if (i->parent) set_orphan_rear(i); 00185 continue; 00186 } 00187 00188 if (i->tr_cap > 0) 00189 { 00190 if (!i->parent || i->is_sink) 00191 { 00192 i->is_sink = 0; 00193 for (a=i->first; a; a=a->next) 00194 { 00195 j = a->head; 00196 if (!j->is_marked) 00197 { 00198 if (j->parent == a->sister) set_orphan_rear(j); 00199 if (j->parent && j->is_sink && a->r_cap > 0) set_active(j); 00200 } 00201 } 00202 add_to_changed_list(i); 00203 } 00204 } 00205 else 00206 { 00207 if (!i->parent || !i->is_sink) 00208 { 00209 i->is_sink = 1; 00210 for (a=i->first; a; a=a->next) 00211 { 00212 j = a->head; 00213 if (!j->is_marked) 00214 { 00215 if (j->parent == a->sister) set_orphan_rear(j); 00216 if (j->parent && !j->is_sink && a->sister->r_cap > 0) set_active(j); 00217 } 00218 } 00219 add_to_changed_list(i); 00220 } 00221 } 00222 i->parent = TERMINAL; 00223 i -> TS = TIME; 00224 i -> DIST = 1; 00225 } 00226 00227 //test_consistency(); 00228 00229 /* adoption */ 00230 while ((np=orphan_first)) 00231 { 00232 orphan_first = np -> next; 00233 i = np -> ptr; 00234 nodeptr_block -> Delete(np); 00235 if (!orphan_first) orphan_last = NULL; 00236 if (i->is_sink) process_sink_orphan(i); 00237 else process_source_orphan(i); 00238 } 00239 /* adoption end */ 00240 00241 //test_consistency(); 00242 }
Graph< captype, tcaptype, flowtype >::node * Graph< captype, tcaptype, flowtype >::next_active | ( | ) | [inline, private] |
Definition at line 53 of file maxflow.cpp.
00054 { 00055 node *i; 00056 00057 while ( 1 ) 00058 { 00059 if (!(i=queue_first[0])) 00060 { 00061 queue_first[0] = i = queue_first[1]; 00062 queue_last[0] = queue_last[1]; 00063 queue_first[1] = NULL; 00064 queue_last[1] = NULL; 00065 if (!i) return NULL; 00066 } 00067 00068 /* remove it from the active list */ 00069 if (i->next == i) queue_first[0] = queue_last[0] = NULL; 00070 else queue_first[0] = i -> next; 00071 i -> next = NULL; 00072 00073 /* a node in the list is active iff it has a parent */ 00074 if (i->parent) return i; 00075 } 00076 }
void Graph< captype, tcaptype, flowtype >::process_sink_orphan | ( | node * | i | ) | [private] |
Definition at line 401 of file maxflow.cpp.
00402 { 00403 node *j; 00404 arc *a0, *a0_min = NULL, *a; 00405 int d, d_min = INFINITE_D; 00406 00407 /* trying to find a new parent */ 00408 for (a0=i->first; a0; a0=a0->next) 00409 if (a0->r_cap) 00410 { 00411 j = a0 -> head; 00412 if (j->is_sink && (a=j->parent)) 00413 { 00414 /* checking the origin of j */ 00415 d = 0; 00416 while ( 1 ) 00417 { 00418 if (j->TS == TIME) 00419 { 00420 d += j -> DIST; 00421 break; 00422 } 00423 a = j -> parent; 00424 d ++; 00425 if (a==TERMINAL) 00426 { 00427 j -> TS = TIME; 00428 j -> DIST = 1; 00429 break; 00430 } 00431 if (a==ORPHAN) { d = INFINITE_D; break; } 00432 j = a -> head; 00433 } 00434 if (d<INFINITE_D) /* j originates from the sink - done */ 00435 { 00436 if (d<d_min) 00437 { 00438 a0_min = a0; 00439 d_min = d; 00440 } 00441 /* set marks along the path */ 00442 for (j=a0->head; j->TS!=TIME; j=j->parent->head) 00443 { 00444 j -> TS = TIME; 00445 j -> DIST = d --; 00446 } 00447 } 00448 } 00449 } 00450 00451 if (i->parent = a0_min) 00452 { 00453 i -> TS = TIME; 00454 i -> DIST = d_min + 1; 00455 } 00456 else 00457 { 00458 /* no parent is found */ 00459 add_to_changed_list(i); 00460 00461 /* process neighbors */ 00462 for (a0=i->first; a0; a0=a0->next) 00463 { 00464 j = a0 -> head; 00465 if (j->is_sink && (a=j->parent)) 00466 { 00467 if (a0->r_cap) set_active(j); 00468 if (a!=TERMINAL && a!=ORPHAN && a->head==i) 00469 { 00470 set_orphan_rear(j); // add j to the end of the adoption list 00471 } 00472 } 00473 } 00474 } 00475 }
void Graph< captype, tcaptype, flowtype >::process_source_orphan | ( | node * | i | ) | [private] |
Definition at line 324 of file maxflow.cpp.
00325 { 00326 node *j; 00327 arc *a0, *a0_min = NULL, *a; 00328 int d, d_min = INFINITE_D; 00329 00330 /* trying to find a new parent */ 00331 for (a0=i->first; a0; a0=a0->next) 00332 if (a0->sister->r_cap) 00333 { 00334 j = a0 -> head; 00335 if (!j->is_sink && (a=j->parent)) 00336 { 00337 /* checking the origin of j */ 00338 d = 0; 00339 while ( 1 ) 00340 { 00341 if (j->TS == TIME) 00342 { 00343 d += j -> DIST; 00344 break; 00345 } 00346 a = j -> parent; 00347 d ++; 00348 if (a==TERMINAL) 00349 { 00350 j -> TS = TIME; 00351 j -> DIST = 1; 00352 break; 00353 } 00354 if (a==ORPHAN) { d = INFINITE_D; break; } 00355 j = a -> head; 00356 } 00357 if (d<INFINITE_D) /* j originates from the source - done */ 00358 { 00359 if (d<d_min) 00360 { 00361 a0_min = a0; 00362 d_min = d; 00363 } 00364 /* set marks along the path */ 00365 for (j=a0->head; j->TS!=TIME; j=j->parent->head) 00366 { 00367 j -> TS = TIME; 00368 j -> DIST = d --; 00369 } 00370 } 00371 } 00372 } 00373 00374 if (i->parent = a0_min) 00375 { 00376 i -> TS = TIME; 00377 i -> DIST = d_min + 1; 00378 } 00379 else 00380 { 00381 /* no parent is found */ 00382 add_to_changed_list(i); 00383 00384 /* process neighbors */ 00385 for (a0=i->first; a0; a0=a0->next) 00386 { 00387 j = a0 -> head; 00388 if (!j->is_sink && (a=j->parent)) 00389 { 00390 if (a0->sister->r_cap) set_active(j); 00391 if (a!=TERMINAL && a!=ORPHAN && a->head==i) 00392 { 00393 set_orphan_rear(j); // add j to the end of the adoption list 00394 } 00395 } 00396 } 00397 } 00398 }
void Graph< captype, tcaptype, flowtype >::reallocate_arcs | ( | ) | [private] |
num is the number of new nodes
Definition at line 87 of file graph.cpp.
00088 { 00089 int arc_num_max = (int)(arc_max - arcs); 00090 int arc_num = (int)(arc_last - arcs); 00091 arc* arcs_old = arcs; 00092 00093 arc_num_max += arc_num_max / 2; if (arc_num_max & 1) arc_num_max ++; 00094 arcs = (arc*) realloc(arcs_old, arc_num_max*sizeof(arc)); 00095 if (!arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); } 00096 00097 arc_last = arcs + arc_num; 00098 arc_max = arcs + arc_num_max; 00099 00100 if (arcs != arcs_old) 00101 { 00102 node* i; 00103 arc* a; 00104 for (i=nodes; i<node_last; i++) 00105 { 00106 if (i->first) i->first = (arc*) ((char*)i->first + (((char*) arcs) - ((char*) arcs_old))); 00107 } 00108 for (a=arcs; a<arc_last; a++) 00109 { 00110 if (a->next) a->next = (arc*) ((char*)a->next + (((char*) arcs) - ((char*) arcs_old))); 00111 a->sister = (arc*) ((char*)a->sister + (((char*) arcs) - ((char*) arcs_old))); 00112 } 00113 } 00114 }
void Graph< captype, tcaptype, flowtype >::reallocate_nodes | ( | int | num | ) | [private] |
monotonically increasing global counter
Definition at line 63 of file graph.cpp.
00064 { 00065 int node_num_max = (int)(node_max - nodes); 00066 node* nodes_old = nodes; 00067 00068 node_num_max += node_num_max / 2; 00069 if (node_num_max < node_num + num) node_num_max = node_num + num; 00070 nodes = (node*) realloc(nodes_old, node_num_max*sizeof(node)); 00071 if (!nodes) { if (error_function) (*error_function)("Not enough memory!"); exit(1); } 00072 00073 node_last = nodes + node_num; 00074 node_max = nodes + node_num_max; 00075 00076 if (nodes != nodes_old) 00077 { 00078 arc* a; 00079 for (a=arcs; a<arc_last; a++) 00080 { 00081 a->head = (node*) ((char*)a->head + (((char*) nodes) - ((char*) nodes_old))); 00082 } 00083 } 00084 }
void Graph< captype, tcaptype, flowtype >::remove_from_changed_list | ( | node_id | i | ) | [inline] |
If changed_list is not NULL while calling maxflow(), then the algorithm keeps a list of nodes which could potentially have changed their segmentation label. Nodes which are not in the list are guaranteed to keep their old segmentation label (SOURCE or SINK). Example usage:
typedef Graph<int,int,int> G; G* g = new Graph(nodeNum, edgeNum); Block<G::node_id>* changed_list = new Block<G::node_id>(128);
... //! add nodes and edges
g->maxflow(); //! first call should be without arguments for (int iter=0; iter<10; iter++) { ... //! change graph, call mark_node() accordingly
g->maxflow(true, changed_list); G::node_id* ptr; for (ptr=changed_list->ScanFirst(); ptr; ptr=changed_list->ScanNext()) { G::node_id i = *ptr; assert(i>=0 && i<nodeNum); g->remove_from_changed_list(i); ! do something with node i... if (g->what_segment(i) == G::SOURCE) { ... } } changed_list->Reset(); } delete changed_list;
NOTE:
Definition at line 245 of file graph.h.
00246 { 00247 assert(i>=0 && i<node_num && nodes[i].is_in_changed_list); 00248 nodes[i].is_in_changed_list = 0; 00249 }
void Graph< captype, tcaptype, flowtype >::reset | ( | ) |
Removes all nodes and edges. After that functions add_node() and add_edge() must be called again.
Advantage compared to deleting Graph and allocating it again: no calls to delete/new (which could be quite slow).
If the graph structure stays the same, then an alternative is to go through all nodes/edges and set new residual capacities (see functions below).
Definition at line 46 of file graph.cpp.
00047 { 00048 node_last = nodes; 00049 arc_last = arcs; 00050 node_num = 0; 00051 00052 if (nodeptr_block) 00053 { 00054 delete nodeptr_block; 00055 nodeptr_block = NULL; 00056 } 00057 00058 maxflow_iteration = 0; 00059 flow = 0; 00060 }
void Graph< captype, tcaptype, flowtype >::restore_saved | ( | ) | [inline] |
Definition at line 412 of file graph.h.
00412 { 00413 for(int i=0;i<save.nodes.size();++i){ 00414 restore_node(save.nodes[i].dest,save.nodes[i].saved); 00415 }; 00416 for(int i=0;i<save.arcs.size();++i){ 00417 restore_arc(save.arcs[i].dest,save.arcs[i].saved); 00418 }; 00419 flow = save.flow; 00420 maxflow_iteration = save.maxflow_iteration; 00421 for(int i=0;i<2;++i){ 00422 queue_first[i] = save.queue_first[i]; 00423 queue_last[i] = save.queue_last[i]; 00424 }; 00425 TIME = save.TIME; 00426 };
void Graph< captype, tcaptype, flowtype >::set_active | ( | node * | i | ) | [inline, private] |
functions for processing active list
Definition at line 35 of file maxflow.cpp.
00036 { 00037 if (!i->next) 00038 { 00039 /* it's not in the list yet */ 00040 if (queue_last[1]) queue_last[1] -> next = i; 00041 else queue_first[1] = i; 00042 queue_last[1] = i; 00043 i -> next = i; 00044 } 00045 }
void Graph< captype, tcaptype, flowtype >::set_orphan_front | ( | node * | i | ) | [inline, private] |
functions for processing orphans list
Definition at line 81 of file maxflow.cpp.
00082 { 00083 nodeptr *np; 00084 i -> parent = ORPHAN; 00085 np = nodeptr_block -> New(); 00086 np -> ptr = i; 00087 np -> next = orphan_first; 00088 orphan_first = np; 00089 }
void Graph< captype, tcaptype, flowtype >::set_orphan_rear | ( | node * | i | ) | [inline, private] |
add to the beginning of the list
Definition at line 92 of file maxflow.cpp.
00093 { 00094 nodeptr *np; 00095 i -> parent = ORPHAN; 00096 np = nodeptr_block -> New(); 00097 np -> ptr = i; 00098 if (orphan_last) orphan_last -> next = np; 00099 else orphan_first = np; 00100 orphan_last = np; 00101 np -> next = NULL; 00102 }
void Graph< captype, tcaptype, flowtype >::start_save | ( | ) | [inline] |
Definition at line 375 of file graph.h.
00375 { 00376 for(int i=0;i<save.nodes.size();++i){ 00377 save.nodes[i].dest->is_saved = false; 00378 }; 00379 for(int i=0;i<save.arcs.size();++i){ 00380 save.arcs[i].dest->is_saved = false; 00381 }; 00382 save.nodes.clear(); 00383 save.arcs.clear(); 00384 save.flow = flow; 00385 save.maxflow_iteration = maxflow_iteration; 00386 for(int i=0;i<2;++i){ 00387 save.queue_first[i] = queue_first[i]; 00388 save.queue_last[i] = queue_last[i]; 00389 }; 00390 save.TIME = TIME; 00391 save.started = true; 00392 };
void Graph< captype, tcaptype, flowtype >::stop_save | ( | ) | [inline] |
void Graph< captype, tcaptype, flowtype >::test_consistency | ( | node * | current_node = NULL |
) | [private] |
Definition at line 618 of file maxflow.cpp.
00619 { 00620 node *i; 00621 arc *a; 00622 int r; 00623 int num1 = 0, num2 = 0; 00624 00625 // test whether all nodes i with i->next!=NULL are indeed in the queue 00626 for (i=nodes; i<node_last; i++) 00627 { 00628 if (i->next || i==current_node) num1 ++; 00629 } 00630 for (r=0; r<3; r++) 00631 { 00632 i = (r == 2) ? current_node : queue_first[r]; 00633 if (i) 00634 for ( ; ; i=i->next) 00635 { 00636 num2 ++; 00637 if (i->next == i) 00638 { 00639 if (r<2){ assert(i == queue_last[r]); 00640 }else assert(i == current_node); 00641 break; 00642 } 00643 } 00644 } 00645 assert(num1 == num2); 00646 00647 for (i=nodes; i<node_last; i++) 00648 { 00649 // test whether all edges in seach trees are non-saturated 00650 if (i->parent == NULL) {} 00651 else if (i->parent == ORPHAN) {} 00652 else if (i->parent == TERMINAL) 00653 { 00654 if (!i->is_sink){ assert(i->tr_cap > 0); 00655 }else assert(i->tr_cap < 0); 00656 } 00657 else 00658 { 00659 if (!i->is_sink){ assert (i->parent->sister->r_cap > 0); 00660 }else assert (i->parent->r_cap > 0); 00661 } 00662 // test whether passive nodes in search trees have neighbors in 00663 // a different tree through non-saturated edges 00664 if (i->parent && !i->next) 00665 { 00666 if (!i->is_sink) 00667 { 00668 assert(i->tr_cap >= 0); 00669 for (a=i->first; a; a=a->next) 00670 { 00671 if (a->r_cap > 0) assert(a->head->parent && !a->head->is_sink); 00672 } 00673 } 00674 else 00675 { 00676 assert(i->tr_cap <= 0); 00677 for (a=i->first; a; a=a->next) 00678 { 00679 if (a->sister->r_cap > 0) assert(a->head->parent && a->head->is_sink); 00680 } 00681 } 00682 } 00683 // test marking invariants 00684 if (i->parent && i->parent!=ORPHAN && i->parent!=TERMINAL) 00685 { 00686 assert(i->TS <= i->parent->head->TS); 00687 if (i->TS == i->parent->head->TS) assert(i->DIST > i->parent->head->DIST); 00688 } 00689 } 00690 }
Graph< captype, tcaptype, flowtype >::termtype Graph< captype, tcaptype, flowtype >::what_segment | ( | node_id | i, | |
termtype | default_segm = SOURCE | |||
) | [inline] |
After the maxflow is computed, this function returns to which segment the node 'i' belongs (Graph<captype,tcaptype,flowtype>::SOURCE or Graph<captype,tcaptype,flowtype>::SINK).
Occasionally there may be several minimum cuts. If a node can be assigned to both the source and the sink, then default_segm is returned.
Definition at line 596 of file graph.h.
00597 { 00598 if (nodes[i].parent) 00599 { 00600 return (nodes[i].is_sink) ? SINK : SOURCE; 00601 } 00602 else 00603 { 00604 return default_segm; 00605 } 00606 }
Block<node_id>* Graph< captype, tcaptype, flowtype >::changed_list [private] |
void(* Graph< captype, tcaptype, flowtype >::error_function)(char *) [private] |
int Graph< captype, tcaptype, flowtype >::maxflow_iteration [private] |
DBlock<nodeptr>* Graph< captype, tcaptype, flowtype >::nodeptr_block [private] |
const int Graph< captype, tcaptype, flowtype >::NODEPTR_BLOCK_SIZE = 128 [static, private] |
nodeptr* Graph< captype, tcaptype, flowtype >::orphan_first [private] |
nodeptr * Graph< captype, tcaptype, flowtype >::orphan_last [private] |
node* Graph< captype, tcaptype, flowtype >::queue_first[2] [private] |
node * Graph< captype, tcaptype, flowtype >::queue_last[2] [private] |
graph_save Graph< captype, tcaptype, flowtype >::save |